package chapter1.exe;

import java.util.Iterator;
import java.util.NoSuchElementException;


/** 注意实现队列的时候，使用数组，但可以循环使用数组
 * @author E440
 *
 * @param <Item>
 */
public class ResizingArrayQueueMy<Item> implements Iterable<Item> {

	private Item[] q;       // queue elements
    private int N;          // number of elements on queue
    private int first;      // index of first element of queue
    private int last;       // index of next available slot
	
	public ResizingArrayQueueMy(){
		q=(Item[])new Object[2];
		first=0;
		last=0;
		N=0;
	}
	
	boolean isEmpty(){
		return N==0;
	}
	
	public int size(){
		return N;
	}
	
	public void resize(int max){
		assert max>=N;
		Item[] newArray=(Item[]) new Object[max];
		for(int i=0;i<N;i++){
			newArray[i]=q[(first+i)%q.length];
		}
		first=0;
		last=N;
		q=newArray;
	}
	
	public void enqueue(Item item){
		q[last++]=item;
		if(last==q.length)
			last=0;
		N++;
		if(N>=q.length/2){
			resize(N*2);
		}
	}
	
	public Item dequeue(){
		if(isEmpty()){
			throw new NoSuchElementException();
		}
		N--;
		Item oldFirst=q[first];
		q[first]=null;
		N--;
		first++;
		if(first==q.length) first=0;
		
		if(N>0 && N*4<=q.length){
			resize(2*N);
		}
		return oldFirst;
	}
	
	public Item peek(){
		return q[first];
	}
	
	
	@Override
	public Iterator<Item> iterator() {
		// TODO Auto-generated method stub
		Iterator<Item> it=new Iterator<Item>() {
		int begin=first;
		int n=N;
			@Override
			public boolean hasNext() {
				// TODO Auto-generated method stub
				return !(n==0);
			}

			@Override
			public Item next() {
				if(!hasNext()){
					throw new NoSuchElementException();
				}
				Item item=q[begin];
				begin++;
				if(begin==q.length){
					begin=0;
				}
				return item;
			}

			@Override
			public void remove() {
				// TODO Auto-generated method stub
				
			}
		};
		return null;
	}
	
	
	
}
